package com.levi.sort;

/**
 * @author shentong
 * @date 2021/8/31 21:30
 * @Description 插入排序
 * 思路 ：有一个无序的数组，把里面的元素一次往一个有序的数组里面放，通过循环比较来寻找其中的位置
 * 1.第一个元素直接在有序的数组中，从第二个开始放，例如下标是i，先跟前面的元素 i-1 比较，如果arr[i-1]比arr[i]大,就让arr[i]=arr[i-1] ,即前面的值往后移一位
 * 2.然后 i-- ，即然后跟前一位的前一位进行比较
 *
 * 插入排序的问题:如果最小的数在数组的最后一位，那么最后一次排序需要移动的次数最很多，效率不高,所以针对这个问题引出【希尔排序】
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        long begin = System.currentTimeMillis();
        insertSort(arr);
        long end = System.currentTimeMillis();
//        print(arr);
        System.out.printf("80000个数字用插入排序所消耗的时间是:%d毫秒\n",end-begin);//677毫秒
    }

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) { //要从数组的第二个元素开始，所以这里是 i = 1
            int insertIndex = i - 1;  //要插入的元素的前一个索引，因为要先跟前一个比较
            int insertValue = arr[i]; // 先把要插入的元素的值保存到一个变量中，后面要使用
            //insertIndex >= 0 这个条件是防止数组越界
            //如果要插入的值比他前面的值小，就跟他前面的前面进行比较
            while (insertIndex >= 0 && insertValue<arr[insertIndex]) {
                arr[insertIndex + 1 ] = arr[insertIndex];
                insertIndex--;
            }
            //退出循环的时候，说明已经找到位置了，这个位置就是insertIndex + 1
            arr[insertIndex + 1] = insertValue;
        }
    }

    private static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i+" ");
        }
        System.out.println();
    }
}
